package com.leetcode.partition9;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/11/12 10:49
 */
public class LC877石子游戏 {

    public static boolean stoneGame(int[] piles) {
//        return dynamicProgramming(piles);
        int[][] memo = new int[502][502];
        Arrays.stream(memo).forEach(val -> Arrays.fill(val, Integer.MIN_VALUE));
        return memoization(0, piles.length - 1, piles, memo) >= 0;
    }

    public static void main(String[] args) {
//        int[] piles = {3, 7, 2, 3};
//        int[] piles = {5, 3, 4, 5};
        int[] piles = {4, 2, 10, 2, 3, 1, 21, 9, 9};
        System.out.println(stoneGame(piles));
    }

    private static boolean dynamicProgramming(int[] piles) {
        //dp[i][j]表示在双方都做最好的选择情况下，先手与后手的最大得分差
        int[][] dp = new int[piles.length + 2][piles.length + 2];
        for (int length = 1; length <= piles.length; length++) {
            for (int left = 1; left + length - 1 <= piles.length; left++) {
                int right = left + length - 1;
                //piles[left - 1] - dp[left + 1][right]：从左端取石子，拿完后，原来的后手变先手，从[left + 1, right]区间做最优策略
                dp[left][right] = Math.max(piles[left - 1] - dp[left + 1][right], piles[right - 1] - dp[left][right - 1]);
            }
        }
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return dp[1][piles.length] > 0;
    }

    private static int memoization(int left, int right, int[] piles, int[][] memo) {
        if (left == right) return piles[left];
        //记忆化搜索，memo含义同dp一样
        if (memo[left][right] != Integer.MIN_VALUE) return memo[left][right];
        int leftScore = piles[left] - memoization(left + 1, right, piles, memo);
        int rightScore = piles[right] - memoization(left, right - 1, piles, memo);
        return memo[left][right] = Math.max(leftScore, rightScore);
    }
}
